
#define WRITE_DEBUG_INFO

using System;
using System.Collections.Generic;
using NUnit.Framework;

namespace ProgrammingLanguageNr1
{
	public class Parser
	{
		public Parser (List<Token> tokens, ErrorHandler errorHandler)
		{
			Assert.IsNotNull(tokens);
			m_tokens = tokens;
			m_errorHandler = errorHandler;
			
			m_nextTokenIndex = 0;
			
			m_lookahead = new Token[k];
			m_lookaheadIndex = 0;
			
			//Fill lookahead buffer:
			for (int i = 0; i < k; i++) {
				consumeCurrentToken();
			}
			
			m_programAST = null;
			m_isInsideFunctionDefinition = false;
			m_processed = false;
		}
		
		public void process() {
			
			if(m_processed) {
				throw new InvalidOperationException("Has already processed tokens!");
			}
			
			if(m_tokens.Count == 0) {
				throw new InvalidOperationException("No tokens to process!");
			}
			
			program();
			m_processed = true;
		}
		
		private void program() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("program");
#endif
			
			m_programAST = statementList();
		}
		
		private AST statementList() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("statement list");
#endif
			
			AST statementListTree = new AST(new Token(Token.TokenType.STATEMENT_LIST, "<STATEMENT_LIST>"));
			
			while (lookAheadType(1) != Token.TokenType.EOF &&
				   lookAheadType(1) != Token.TokenType.BLOCK_END) 
			{
				AST statementTree = statement();
				if(statementTree != null) {
					statementListTree.addChild(statementTree);
				}
				else {
#if WRITE_DEBUG_INFO
					Console.WriteLine("null statement");
#endif					
				}
			}
			
			return statementListTree;
		}
		
		private AST statement() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("statement");
#endif
			AST statementTree = null;
			
			try {
				statementTree = figureOutStatementType();
			}
			catch(Error e) {
				m_errorHandler.errorOccured(e);
#if WRITE_DEBUG_INFO
				Console.WriteLine("Error: " + e.getMessage());
#endif
				skipStuffUntilNextLine();
			}
			
			return statementTree;
		}
			
		private AST figureOutStatementType() {
			AST statementTree = null;
			
			if ( lookAheadType(1) == Token.TokenType.NAME &&
				 lookAheadType(2) == Token.TokenType.NAME &&
				 lookAheadType(3) == Token.TokenType.PARANTHESIS_LEFT ) 
			{
				statementTree = functionDeclaration();
				checkThatItsTheEndOfTheLine();
			}
			else if (lookAheadType(1) == Token.TokenType.NAME &&
					 lookAheadType(2) == Token.TokenType.NAME) 
			{
				if (lookAheadType(3) == Token.TokenType.ASSIGNMENT) {
					statementTree = declarationAndAssignment();
					checkThatItsTheEndOfTheLine();
				} else {
					statementTree = declaration();
					checkThatItsTheEndOfTheLine();
				}
			}
			else if (lookAheadType(1) == Token.TokenType.NAME)
			{
				if (lookAheadType(2) == Token.TokenType.ASSIGNMENT) {
					statementTree = assignment();
					checkThatItsTheEndOfTheLine();
				} else {
					statementTree = expression();
					checkThatItsTheEndOfTheLine(); // makes the bodies of if-statements require new line for statements
				}
			}
			else if (lookAheadType(1) == Token.TokenType.NUMBER ||
					 lookAheadType(1) == Token.TokenType.PARANTHESIS_LEFT) 
			{
				statementTree = expression();
				checkThatItsTheEndOfTheLine(); // see above
			}				
			else if (lookAheadType(1) == Token.TokenType.IF) {
				statementTree = ifThenElse();
			}
			else if (lookAheadType(1) == Token.TokenType.RETURN) {
				statementTree = returnFromFunction();
			}
			else if (lookAheadType(1) == Token.TokenType.NEW_LINE) {
				match(Token.TokenType.NEW_LINE); // just skip
			}
			else {
				
			}
			
			return statementTree;
		}
		
		private void checkThatItsTheEndOfTheLine() {
			if (lookAheadType(1) == Token.TokenType.EOF) {
				match(Token.TokenType.EOF);
			}
			else if(lookAheadType(1) == Token.TokenType.NEW_LINE) {
				match(Token.TokenType.NEW_LINE);
			} else {
				throw new Error("Can't understand the tokens at the end of the line.", Error.ErrorType.SYNTAX, lookAhead(1).LineNr, lookAhead(1).LinePosition);
			}
		}
		
		private void skipStuffUntilNextLine() {
			while(	lookAheadType(1) != Token.TokenType.NEW_LINE &&
					lookAheadType(1) != Token.TokenType.EOF ) 
			{
				consumeCurrentToken();
			}
		}
		
		private AST expression() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("expression");
#endif		

			return booleanExpression();	
		}
		
		private AST booleanExpression() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("boolean expression");
#endif
			
			AST lhs = comparisonExpression();
			
			if ( lookAhead(1).getTokenString() == "&&" ||
				 lookAhead(1).getTokenString() == "||"
				)
			{
				Token operatorToken = match(Token.TokenType.OPERATOR);
				AST rhs = comparisonExpression();
			
				AST booleanExpressionTree = new AST(operatorToken);
				booleanExpressionTree.addChild(lhs);
				booleanExpressionTree.addChild(rhs);
				return booleanExpressionTree;
				
			} else {
				return lhs;
			}
		}
		
		private AST comparisonExpression() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("comparison expression");
#endif
			
			AST lhs = plusOrMinusExpression();
			
			if ( lookAhead(1).getTokenString() == "<" ||
				 lookAhead(1).getTokenString() == ">" ||
				 lookAhead(1).getTokenString() == "<=" ||
				 lookAhead(1).getTokenString() == ">=" ||
				 lookAhead(1).getTokenString() == "!=" ||
				 lookAhead(1).getTokenString() == "=="
				)
			{
				Token operatorToken = match(Token.TokenType.OPERATOR);
				AST rhs = plusOrMinusExpression();
			
				AST comparisonExpressionTree = new AST(operatorToken);
				comparisonExpressionTree.addChild(lhs);
				comparisonExpressionTree.addChild(rhs);
				return comparisonExpressionTree;
				
			} else {
				return lhs;
			}
		}
		
		private AST plusOrMinusExpression() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("plus or minus expression");
#endif
		
			AST lhs = multiplicationExpression();
			
			if ( lookAhead(1).getTokenString() == "+" ||
				 lookAhead(1).getTokenString() == "-" ) 
			{
				Token operatorToken = match(Token.TokenType.OPERATOR);
				AST rhs = plusOrMinusExpression();
				
				AST plusMinusExpressionTree = new AST(operatorToken);
				plusMinusExpressionTree.addChild(lhs);
				plusMinusExpressionTree.addChild(rhs);
				return plusMinusExpressionTree;
			} else {
				return lhs;
			}
		}
		
		private AST multiplicationExpression() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("multiplication expression");
#endif
			
			AST lhs = parenthesisExpression();
			
			if ( lookAhead(1).getTokenString() == "*" ||
				 lookAhead(1).getTokenString() == "/" ) 
			{
				Token operatorToken = match(Token.TokenType.OPERATOR);			
				
				AST rhs = multiplicationExpression();
				
				AST multiplicationTree = new AST(operatorToken);
				multiplicationTree.addChild(lhs);
				multiplicationTree.addChild(rhs);
				return multiplicationTree;
				
			} else {
				return lhs;
			}
		}
		
		private AST parenthesisExpression() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("parenthesis expression");
#endif		
			AST lhs;
				
			if (lookAheadType(1) == Token.TokenType.PARANTHESIS_LEFT) {
#if WRITE_DEBUG_INFO
			Console.WriteLine("paranthesis left");
#endif
				match(Token.TokenType.PARANTHESIS_LEFT);
				lhs = expression();
#if WRITE_DEBUG_INFO
			Console.WriteLine("paranthesis right");
#endif
				match(Token.TokenType.PARANTHESIS_RIGHT);
			} else {
				return operand();
			}
			
			if (lookAheadType(1) == Token.TokenType.OPERATOR) { // two parenthesis expressions with an operator between them
				Token operatorToken = match(Token.TokenType.OPERATOR);
				
				AST rightParenthesisTree = expression();
				
				AST duoParenthesisTree = new AST(operatorToken);
				duoParenthesisTree.addChild(lhs);
				duoParenthesisTree.addChild(rightParenthesisTree);
				return duoParenthesisTree;
			} else {
				return lhs;
			}
		}
		
		private AST operand() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("operand");
#endif
			
			AST operandTree = null;
		
			if (lookAheadType(1) == Token.TokenType.NAME && 
				lookAheadType(2) == Token.TokenType.PARANTHESIS_LEFT) 
			{
				operandTree = functionCall();
			}
			else if (lookAheadType(1) == Token.TokenType.NAME) 
			{
				Token operandToken = match(Token.TokenType.NAME);
				operandTree = new AST(operandToken);
			}
			else if (lookAheadType(1) == Token.TokenType.NUMBER) 
			{
				Token operandToken = match(Token.TokenType.NUMBER);
				operandTree = new AST(operandToken);
			}
			else if (lookAheadType(1) == Token.TokenType.QUOTED_STRING) 
			{
				Token operandToken = match(Token.TokenType.QUOTED_STRING);
				operandTree = new AST(operandToken);
			}
			else if (lookAheadType(1) == Token.TokenType.OPERATOR &&
					 lookAhead(1).getTokenString() == "-")
			{
				operandTree = negativeExpression();
			}
			else {
				
			}
			
			return operandTree;
		}
		
		private AST negativeExpression() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("negative expression");
#endif		
			match(Token.TokenType.OPERATOR); // the minus sign
			
			AST negativeExpressionTree = new AST(new Token(Token.TokenType.OPERATOR, "*"));
			AST minusSign = new AST(new Token(Token.TokenType.NUMBER, "-1")); 
			AST expressionTree = parenthesisExpression(); 
			//operand();
			negativeExpressionTree.addChild(minusSign);
			negativeExpressionTree.addChild(expressionTree);
			
			return negativeExpressionTree;
		}
		
		private AST quotedString() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("quoted string");
#endif
			
			Token token = match(Token.TokenType.QUOTED_STRING);
			return new AST(token);
		}
		
		private AST functionCall() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("function call");
#endif
			
			Token nameToken = match(Token.TokenType.NAME);
			match(Token.TokenType.PARANTHESIS_LEFT);
			
			AST functionCallTree = 
				new AST(new Token(Token.TokenType.FUNCTION_CALL, nameToken.getTokenString()));
			
			functionCallTree.getToken().LineNr = nameToken.LineNr;
			functionCallTree.getToken().LinePosition = nameToken.LinePosition;
			
			if (lookAheadType(1) != Token.TokenType.PARANTHESIS_RIGHT) {

				while(true) {
					
					AST expressionTree = expression();
					
					if(expressionTree != null) 
					{
						functionCallTree.addChild(expressionTree); // add arguments as subtrees
					} 
					else 
					{
						throw new Error("Something is wrong with the argument list", Error.ErrorType.SYNTAX,
							lookAhead(1).LineNr, lookAhead(1).LinePosition);
					}
					
					if (lookAheadType(1) == Token.TokenType.COMMA) {
						match(Token.TokenType.COMMA);
						continue;
					} else {
						
						// Is something wrong?
						if( lookAheadType(1) == Token.TokenType.NEW_LINE ||
							lookAheadType(1) == Token.TokenType.EOF ) 
						{
							throw new Error("Ending parenthesis is missing in function call"
								, Error.ErrorType.SYNTAX,
								lookAhead(1).LineNr, lookAhead(1).LinePosition);
						}
						else if( lookAheadType(1) == Token.TokenType.NAME ||
								 lookAheadType(1) == Token.TokenType.QUOTED_STRING ||
								 lookAheadType(1) == Token.TokenType.NUMBER ) 
						{
							throw new Error("Comma is missing in argument list"
								, Error.ErrorType.SYNTAX,
								lookAhead(1).LineNr, lookAhead(1).LinePosition);
						}
						
						break;
					}
				}
			}
			
			match(Token.TokenType.PARANTHESIS_RIGHT);
			
			return functionCallTree;
		}
		
		private AST ifThenElse() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("if block");
#endif
			AST_IfNode ifThenElseTree = null;
			
			try {
				match(Token.TokenType.IF);
				ifThenElseTree = new AST_IfNode(new Token(Token.TokenType.IF, "if"));
				match(Token.TokenType.PARANTHESIS_LEFT);
				ifThenElseTree.addChild(expression()); // child 0
				match(Token.TokenType.PARANTHESIS_RIGHT);
				allowLineBreak();
				match(Token.TokenType.BLOCK_BEGIN);
				ifThenElseTree.addChild(statementList()); // child 1
				match(Token.TokenType.BLOCK_END);
				allowLineBreak();
				
				if (lookAheadType(1) == Token.TokenType.ELSE) {
#if WRITE_DEBUG_INFO
				Console.WriteLine("else block");
#endif
					match(Token.TokenType.ELSE);
					allowLineBreak();
					match(Token.TokenType.BLOCK_BEGIN);
					allowLineBreak();
					ifThenElseTree.addChild(statementList()); // child 2
					match(Token.TokenType.BLOCK_END);
				}
			}
			catch(Error e) {
				// The error caught here will probably be from the match() function.
				// Since that means we're missing some part of the if-statement we can give a better 
				// error message by throwing a new one.
				throw new Error("If statement isn't complete", Error.ErrorType.SYNTAX, e.getLineNr(), e.getLinePosition());
			}
			
			return ifThenElseTree;
		}
		
		private void allowLineBreak() {
			if (lookAheadType(1) == Token.TokenType.NEW_LINE) {
				match(Token.TokenType.NEW_LINE); // allow line break
			}
		}
		
		private AST returnFromFunction() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("return from function");
#endif			
			
			AST returnTree = new AST(match(Token.TokenType.RETURN));
			AST returnExpression = expression();
			
			if(returnExpression != null) {
				returnTree.addChild(returnExpression);
			}
			else {
				throw new Error("No expression in return statement", Error.ErrorType.SYNTAX,
					lookAhead(1).LineNr, lookAhead(1).LinePosition);
			}
			
			return returnTree;						
		}
		
		private AST declaration() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("declaration");
#endif
			
			Token typeName = match(Token.TokenType.NAME);
			Token variableName = match(Token.TokenType.NAME);
			
			AST declarationTree = new AST(new Token(Token.TokenType.VAR_DECLARATION, "<VAR_DECL>"));
			declarationTree.addChild(typeName); // child 0
			declarationTree.addChild(variableName); // child 1
			
			return declarationTree;
		}
		
		private AST assignment() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("assignment");
#endif
			
			Token nameToken = match(Token.TokenType.NAME);
			Token assignmentToken = match(Token.TokenType.ASSIGNMENT);
			
			AST expressionTree = expression();
			
			if(expressionTree != null) {
				AST assignmentTree = new AST(assignmentToken);
				assignmentTree.addChild(nameToken); // child 0
				assignmentTree.addChild(expressionTree); // child 1
			
				return assignmentTree;
			}
			else {
				throw new Error("Missing expression in assignment", Error.ErrorType.SYNTAX,
					lookAhead(1).LineNr, lookAhead(1).LinePosition);
			}
		}
		
		private AST declarationAndAssignment() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("declaration and assignment");
#endif
			
			AST declarationTree = declaration();
			Token assignmentToken = match(Token.TokenType.ASSIGNMENT);
			AST expressionTree = expression();
			
			if(expressionTree != null) {
				AST assignmentTree = new AST(assignmentToken);
				Token nameToken = declarationTree.getChild(1).getToken();
				assignmentTree.addChild(nameToken); // child 0
				assignmentTree.addChild(expressionTree); // child 1
				
				AST declarationAndAssignmentTree = 
				new AST(new Token(Token.TokenType.STATEMENT_LIST, "<DECLARATION_AND_ASSIGNMENT>"));
				declarationAndAssignmentTree.addChild(declarationTree);
				declarationAndAssignmentTree.addChild(assignmentTree);
			
				return declarationAndAssignmentTree;
			} else {
				throw new Error("Missing expression in assignment", Error.ErrorType.SYNTAX,
					lookAhead(1).LineNr, lookAhead(1).LinePosition);
			}
		}
		
		protected AST functionDeclaration() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("function declaration");
#endif
			
			if (m_isInsideFunctionDefinition) {
				throw new Error("Trying to define a function inside a function (are you missing a curly bracket?)", Error.ErrorType.SYNTAX,
					lookAhead(1).LineNr, lookAhead(1).LinePosition);
			} else {
				m_isInsideFunctionDefinition = true;
			}			
			
			AST_FunctionDefinitionNode funcDeclarationTree = 
				new AST_FunctionDefinitionNode(new Token(Token.TokenType.FUNC_DECLARATION, "<FUNC_DECL>"));
			
			funcDeclarationTree.addChild(match(Token.TokenType.NAME)); // child 0 (function return type)
			funcDeclarationTree.addChild(match(Token.TokenType.NAME)); // child 1 (function name)
			
			match(Token.TokenType.PARANTHESIS_LEFT);
			funcDeclarationTree.addChild(parameterList()); // child 2 (parameter list)
			match(Token.TokenType.PARANTHESIS_RIGHT);
			
			allowLineBreak();
			
			try {
				match(Token.TokenType.BLOCK_BEGIN);
			}
			catch(Error e) {
				throw new Error("Missing curly bracket in beginning of function definition", 
					Error.ErrorType.SYNTAX,
					e.getLineNr(), e.getLinePosition());
			}
			
			funcDeclarationTree.addChild(statementList()); // child 3 (function body)
			match(Token.TokenType.BLOCK_END);
			
			m_isInsideFunctionDefinition = false;
			
			return funcDeclarationTree;
		}
		
		protected AST parameterList() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("parameter list");
#endif
			
			AST parameterListTree = new AST(new Token(Token.TokenType.PARAMETER_LIST, "<PARAMETER_LIST>"));
			
			if (lookAheadType(1) != Token.TokenType.PARANTHESIS_RIGHT) {

				while(true) {
					
					AST parameterTree = parameter();
					parameterListTree.addChild(parameterTree);
					
					if (lookAheadType(1) == Token.TokenType.COMMA) {
						match(Token.TokenType.COMMA);
						continue;
					} else {
						break;
					}
				}
			}
			
			return parameterListTree;
		}
		
		protected AST parameter() {
#if WRITE_DEBUG_INFO
			Console.WriteLine("parameter");
#endif
			
			AST parameterTree = new AST(new Token(Token.TokenType.PARAMETER, "<PARAMETER>"));
			
			parameterTree.addChild(match(Token.TokenType.NAME)); // child 0 = type
			parameterTree.addChild(match(Token.TokenType.NAME)); // child 1 = name
			
			return parameterTree;
		}
		
		protected virtual Token match(Token.TokenType expectedTokenType) {
			
			Token matchedToken = lookAhead(1);
			
			if(lookAheadType(1) == expectedTokenType) {
#if WRITE_DEBUG_INFO
			Console.WriteLine("MATCHED TOKEN " + lookAhead(1).getTokenString() + " (line " + lookAhead(1).LineNr + ")");
#endif
				consumeCurrentToken();
				
			} else {
#if WRITE_DEBUG_INFO
			Console.WriteLine("FAILED TO MATCH TOKEN OF TYPE " + expectedTokenType.ToString() + 
					" ...FOUND " + lookAhead(1).getTokenString() + " (line " + lookAhead(1).LineNr + ")");
#endif				
				throw new Error(
					"The code word \"" + lookAhead(1).getTokenString() + "\"" +
					" doesn't match the expected (" + expectedTokenType + ").",
					Error.ErrorType.SYNTAX,
					lookAhead(1).LineNr,
					lookAhead(1).LinePosition);
				
			}
			
			return matchedToken;
		}
		
		public void consumeCurrentToken() {
			
			Token nextToken;
			
			if (m_nextTokenIndex < m_tokens.Count) {
				nextToken = m_tokens[m_nextTokenIndex];
				m_nextTokenIndex++;
			}
			else {
				nextToken = new Token(Token.TokenType.EOF, "<EOF>");
			}
			
			m_lookahead[m_lookaheadIndex] = nextToken;
			m_lookaheadIndex = (m_lookaheadIndex + 1) % k;
		}
		
		public Token lookAhead(int i) {
			return m_lookahead[(m_lookaheadIndex + i - 1) % k];
		}
		
		public Token.TokenType lookAheadType(int i) {
			return lookAhead(i).getTokenType();
		}
		
		public AST getAST() {
			Assert.IsNotNull(m_programAST, "AST is null, this probably means that you haven't called process() on Parser");
			return m_programAST; 
		}
		
		bool m_processed = false;
		List<Token> m_tokens;
		int m_nextTokenIndex;
		
		Token[] m_lookahead;
		int k = 4; // how many lookahead symbols
		int m_lookaheadIndex = 0; // cirkular index
		
		AST m_programAST;
		ErrorHandler m_errorHandler;
		
		bool m_isInsideFunctionDefinition;
	}
}

